Corelab Seminar
2020-2021
Spyros Angelopoulos
Online algorithms with predictions
Abstract.
Online computation is a well-established paradigm that applies in settings in which the input is revealed incrementally, as a sequence of items. Previously studied online models have largely assumed that either the online algorithm has no information about the future input items, or that such information is provided by an overly powerful and error-free oracle. A more recent, and more realistic approach allows the online algorithm access to some natural, but potentially erroneous prediction concerning the input. In this presentation I will discuss some recent contributions to this rapidly growing area, focusing on some classic problems from online search theory and online resource allocation.